Discrete parameter simulation optimization algorithms with applications to admission control with dependent service times

We propose certain discrete parameter variants of well known simulation optimization algorithms. Two of these algorithms are based on the smoothed functional (SF) technique while two others are based on the simultaneous perturbation stochastic approximation (SPSA) method. They differ from each other in the way perturbations are obtained and also the manner in which projections and parameter updates are performed. All our algorithms use two simulations and two-timescale stochastic approximation. As an application setting, we consider the important problem of admission control of packets in communication networks under dependent service times. We consider a discrete time slotted queueing model of the system and consider two different scenarios - one where the service times have a dependence on the system state and the other where they depend on the number of arrivals in a time slot. Under our settings, the simulated objective function appears ill-behaved with multiple local minima and a unique global minimum characterized by a sharp dip in the objective function in a small region of the parameter space. We compare the performance of our algorithms on these settings and observe that the two SF algorithms show the best results overall. In fact, in many cases studied, SF algorithms converge to the global minimum.

Stochastic Algorithms for Discrete Parameter Simulation Optimization

We present two efficient discrete parameter simulation optimization (DPSO) algorithms for the long-run average cost objective. One of these algorithms uses the smoothed functional approximation (SFA) procedure, while the other is based on simultaneous perturbation stochastic approximation (SPSA). The use of SFA for DPSO had not been proposed previously in the literature. Further, both algorithms adopt an interesting technique of random projections that we present here for the first time. We give a proof of convergence of our algorithms. Next, we present detailed numerical experiments on a problem of admission control with dependent service times. We consider two different settings involving parameter sets that have moderate and large sizes, respectively. On the first setting, we also show performance comparisons with the well-studied optimal computing budget allocation (OCBA) algorithm and also the equal allocation algorithm. Note to Practitioners-Even though SPSA and SFA have been devised in the literature for continuous optimization problems, our results indicate that they can be powerful techniques even when they are adapted to discrete optimization settings. OCBA is widely recognized as one of the most powerful methods for discrete optimization when the parameter sets are of small or moderate size. On a setting involving a parameter set of size 100, we observe that when the computing budget is small, both SPSA and OCBA show similar performance and are better in comparison to SFA, however, as the computing budget is increased, SPSA and SFA show better performance than OCBA. Both our algorithms also show good performance when the parameter set has a size of 10(8). SFA is seen to show the best overall performance. Unlike most other DPSO algorithms in the literature, an advantage with our algorithms is that they are easily implementable regardless of the size of the parameter sets and show good performance in both scenarios.

Distributed Simulation Of Flexible Manufacturing Systems

Flexible Manufacturing Systems (FMS), widely considered as the manufacturing technology of the future, are gaining increasing importance due to the immense advantages they provide in terms of cost, quality and productivity over the conventional manufacturing. An FMS is a complex interconnection of capital intensive resources and high levels of system performance is very crucial for survival in a competing environment.Discrete event simulation is one of the most popular methods for performance evaluation of FMS during planning, design and operation phases. Indeed fast simulators are suggested for selection of optimal strategies for flow control (which part type to enter and at what instant), AGV scheduling (which vehicle to carry which part), routing (which machine to process the part) and part selection (which part for processing next). In this paper we develop a C-net based model for an FMS and use the same for distributed discrete event simulation. We illustrate using examples the efficacy of destributed discrete event simulation for the performance evaluation of FMSs.

Design and Performance Evaluation of EXMAN: An EXtended MANchester Data Flow Computer

Data flow computers are high-speed machines in which an instruction is executed as soon as all its operands are available. This paper describes the EXtended MANchester (EXMAN) data flow computer which incorporates three major extensions to the basic Manchester machine. As extensions we provide a multiple matching units scheme, an efficient, implementation of array data structure, and a facility to concurrently execute reentrant routines. A simulator for the EXMAN computer has been coded in the discrete event simulation language, SIMULA 67, on the DEC 1090 system. Performance analysis studies have been conducted on the simulated EXMAN computer to study the effectiveness of the proposed extensions. The performance experiments have been carried out using three sample problems: matrix multiplication, Bresenham's line drawing algorithm, and the polygon scan-conversion algorithm.

Phase-Field Simulation of Fusion Interface Events during Solidification of Dissimilar Welds: Effect of Composition Inhomogeneity

We investigate the events near the fusion interfaces of dissimilar welds using a phase-field model developed for single-phase solidification of binary alloys. The parameters used here correspond to the dissimilar welding of a Ni/Cu couple. The events at the Ni and the Cu interface are very different, which illustrate the importance of the phase diagram through the slope of the liquidus curves. In the Ni side, where the liquidus temperature decreases with increasing alloying, solutal melting of the base metal takes place; the resolidification, with continuously increasing solid composition, is very sluggish until the interface encounters a homogeneous melt composition. The growth difficulty of the base metal increases with increasing initial melt composition, which is equivalent to a steeper slope of the liquidus curve. In the Cu side, the initial conditions result in a deeply undercooled melt and contributions from both constrained and unconstrained modes of growth are observed. The simulations bring out the possibility of nucleation of a concentrated solid phase from the melt, and a secondary melting of the substrate due to the associated recalescence event. The results for the Ni and Cu interfaces can be used to understand more complex dissimilar weld interfaces involving multiphase solidification.

Optimal threshold policies for admission control in communication networks via discrete parameter stochastic approximation

The problem of admission control of packets in communication networks is studied in the continuous time queueing framework under different classes of service and delayed information feedback. We develop and use a variant of a simulation based two timescale simultaneous perturbation stochastic approximation (SPSA) algorithm for finding an optimal feedback policy within the class of threshold type policies. Even though SPSA has originally been designed for continuous parameter optimization, its variant for the discrete parameter case is seen to work well. We give a proof of the hypothesis needed to show convergence of the algorithm on our setting along with a sketch of the convergence analysis. Extensive numerical experiments with the algorithm are illustrated for different parameter specifications. In particular, we study the effect of feedback delays on the system performance.

Dense granular flow down an inclined plane A comparison between the hard particle model and soft particle simulations

The granular flow down an inclined plane is simulated using the discrete element (DE) technique to examine the extent to which the dynamics of an unconfined dense granular flow can be well described by a hard particle model First, we examine the average coordination number for the particles in the flow down an inclined plane using the DE technique using the linear contact model with and without friction, and the Hertzian contact model with friction The simulations show that the average coordination number decreases below 1 for values of the spring stiffness corresponding to real materials, such as sand and glass, even when the angle of inclination is only 10 larger than the angle of repose Additional measures of correlations in the system, such as the fraction of particles with multibody contact, the force ratio (average ratio of the magnitudes of the largest and the second largest force on a particle), and the angle between the two largest forces on the particle, show no evidence of force chains or other correlated motions in the system An analysis of the bond-orientational order parameter indicates that the flow is in the random state, as in event-driven (ED) simulations V Kumaran, J Fluid Mech 632, 107 (2009), J Fluid Mech 632, 145 (2009)] The results of the two simulation techniques for the Bagnold coefficients (ratio of stress and square of the strain rate) and the granular temperature (mean square of the fluctuating velocity) are compared with the theory V Kumaran, J Fluid Mech 632, 107 (2009), J Fluid Mech 632, 145 (2009)] and are found to be in quantitative agreement In addition, we also conduct a comparison of the collision frequency and the distribution of the precollisional relative velocities of particles in contact The strong correlation effects exhibited by these two quantities in event-driven simulations V Kumaran, J Fluid Mech 632, 145 (2009)] are also found in the DE simulations (C) 2010 American Institute of Physics doi 10 1063/1 3504660]

Simulation of ENSO-Related Surface Winds in the Tropical Pacific by an Atmospheric General Circulation Model Forced by Observed Sea Surface Temperatures

The authors present the simulation of the tropical Pacific surface wind variability by a low-resolution (R15 horizontal resolution and 18 vertical levels) version of the Center for Ocean-Land-Atmosphere Interactions, Maryland, general circulation model (GCM) when forced by observed global sea surface temperature. The authors have examined the monthly mean surface winds acid precipitation simulated by the model that was integrated from January 1979 to March 1992. Analyses of the climatological annual cycle and interannual variability over the Pacific are presented. The annual means of the simulated zonal and meridional winds agree well with observations. The only appreciable difference is in the region of strong trade winds where the simulated zonal winds are about 15%-20% weaker than observed, The amplitude of the annual harmonics are weaker than observed over the intertropical convergence zone and the South Pacific convergence zone regions. The amplitudes of the interannual variation of the simulated zonal and meridional winds are close to those of the observed variation. The first few dominant empirical orthogonal functions (EOF) of the simulated, as well as the observed, monthly mean winds are found to contain a targe amount of high-frequency intraseasonal variations, While the statistical properties of the high-frequency modes, such as their amplitude and geographical locations, agree with observations, their detailed time evolution does not. When the data are subjected to a 5-month running-mean filter, the first two dominant EOFs of the simulated winds representing the low-frequency EI Nino-Southern Oscillation fluctuations compare quite well with observations. However, the location of the center of the westerly anomalies associated with the warm episodes is simulated about 15 degrees west of the observed locations. The model simulates well the progress of the westerly anomalies toward the eastern Pacific during the evolution of a warm event. The simulated equatorial wind anomalies are comparable in magnitude to the observed anomalies. An intercomparison of the simulation of the interannual variability by a few other GCMs with comparable resolution is also presented. The success in simulation of the large-scale low-frequency part of the tropical surface winds by the atmospheric GCM seems to be related to the model's ability to simulate the large-scale low-frequency part of the precipitation. Good correspondence between the simulated precipitation and the highly reflective cloud anomalies is seen in the first two EOFs of the 5-month running means. Moreover, the strong correlation found between the simulated precipitation and the simulated winds in the first two principal components indicates the primary role of model precipitation in driving the surface winds. The surface winds simulated by a linear model forced by the GCM-simulated precipitation show good resemblance to the GCM-simulated winds in the equatorial region. This result supports the recent findings that the large-scale part of the tropical surface winds is primarily linear.

Vortex sheet simulation of a plane �canonical� mixing layer

Discrete vortex simulations of the mixing layer carried out in the past have usually involved large induced velocity fluctuations, and thus demanded rather long time-averaging to obtain satisfactory values of Reynolds stresses and third-order moments. This difficulty has been traced here, in part, to the use of discrete vortices to model what in actuality are continuous vortex sheets. We propose here a novel two-dimensional vortex sheet technique for computing mixing layer flow in the limit of infinite Reynolds number. The method divides the vortex sheet into constant-strength linear elements, whose motions are computed using the Biot-Savart law. The downstream far-field is modelled by a steady vorticity distribution derived by application of conical similarity from the solution obtained in a finite computational domain. The boundary condition on the splitter plate is satisfied rigorously using a doublet sheet. The computed large-scale roll-up of the vortex sheet is qualitatively similar to experimentally obtained shadow-graphs of the plane turbulent mixing layer. The mean streamwise velocity profile and the growth rate agree well with experimental data. The presently computed Reynolds stresses and third-order moments are comparable with experimental and previous vortex-dynamical results, without using any external parameter (such as the vortex core-size) of the kind often used in the latter. The computed autocorrelations are qualitatively similar to experimental results along the top and bottom edges of the mixing layer, and show a well-defined periodicity along the centreline. The accuracy of the present computation is independently established by demonstrating negligibly small changes in the five invariants (including the Hamiltonian) in vortex dynamics.

Instability, intermittency, and multiscaling in discrete growth models of kinetic roughening

We show by numerical simulations that discretized versions of commonly studied continuum nonlinear growth equations (such as the Kardar-Parisi-Zhangequation and the Lai-Das Sarma-Villain equation) and related atomistic models of epitaxial growth have a generic instability in which isolated pillars (or grooves) on an otherwise flat interface grow in time when their height (or depth) exceeds a critical value. Depending on the details of the model, the instability found in the discretized version may or may not be present in the truly continuum growth equation, indicating that the behavior of discretized nonlinear growth equations may be very different from that of their continuum counterparts. This instability can be controlled either by the introduction of higher-order nonlinear terms with appropriate coefficients or by restricting the growth of pillars (or grooves) by other means. A number of such ''controlled instability'' models are studied by simulation. For appropriate choice of the parameters used for controlling the instability, these models exhibit intermittent behavior, characterized by multiexponent scaling of height fluctuations, over the time interval during which the instability is active. The behavior found in this regime is very similar to the ''turbulent'' behavior observed in recent simulations of several one- and two-dimensional atomistic models of epitaxial growth.

A fast algorithm for finding frequent episodes in event streams

Frequent episode discovery is a popular framework for mining data available as a long sequence of events. An episode is essentially a short ordered sequence of event types and the frequency of an episode is some suitable measure of how often the episode occurs in the data sequence. Recently,we proposed a new frequency measure for episodes based on the notion of non-overlapped occurrences of episodes in the event sequence, and showed that, such a definition, in addition to yielding computationally efficient algorithms, has some important theoretical properties in connecting frequent episode discovery with HMM learning. This paper presents some new algorithms for frequent episode discovery under this non-overlapped occurrences-based frequency definition. The algorithms presented here are better (by a factor of N, where N denotes the size of episodes being discovered) in terms of both time and space complexities when compared to existing methods for frequent episode discovery. We show through some simulation experiments, that our algorithms are very efficient. The new algorithms presented here have arguably the least possible orders of spaceand time complexities for the task of frequent episode discovery.

Discrete control algorithms for a tubular ammonia reactor

The specific objective of this paper is to develop direct digital control strategies for an ammonia reactor using quadratic regulator theory and compare the performance of the resultant control system with that under conventional PID regulators. The controller design studies are based on a ninth order state-space model obtained from the exact nonlinear distributed model using linearization and lumping approximations. The evaluation of these controllers with reference to their disturbance rejection capabilities and transient response characteristics, is carried out using hybrid computer simulation.

Delay Optimal Event Detection on Ad Hoc Wireless Sensor Networks

We consider a small extent sensor network for event detection, in which nodes periodically take samples and then contend over a random access network to transmit their measurement packets to the fusion center. We consider two procedures at the fusion center for processing the measurements. The Bayesian setting, is assumed, that is, the fusion center has a prior distribution on the change time. In the first procedure, the decision algorithm at the fusion center is network-oblivious and makes a decision only when a complete vector of measurements taken at a sampling instant is available. In the second procedure, the decision algorithm at the fusion center is network-aware and processes measurements as they arrive, but in a time-causal order. In this case, the decision statistic depends on the network delays, whereas in the network-oblivious case, the decision statistic does not. This yields a Bayesian change-detection problem with a trade-off between the random network delay and the decision delay that is, a higher sampling rate reduces the decision delay but increases the random access delay. Under periodic sampling, in the network-oblivious case, the structure of the optimal stopping rule is the same as that without the network, and the optimal change detection delay decouples into the network delay and the optimal decision delay without the network. In the network-aware case, the optimal stopping problem is analyzed as a partially observable Markov decision process, in which the states of the queues and delays in the network need to be maintained. A sufficient decision statistic is the network state and the posterior probability of change having occurred, given the measurements received and the state of the network. The optimal regimes are studied using simulation.

Elasto-plastic analysis of jointed rocks using discrete continuum and equivalent continuum approaches

Results from elasto-plastic numerical simulations of jointed rocks using both the equivalent continuum and discrete continuum approaches are presented, and are compared with experimental measurements. Initially triaxial compression tests on different types of rocks with wide variation in the uniaxial compressive strength are simulated using both the approaches and the results are compared. The applicability and relative merits and limitations of both the approaches for the simulation of jointed rocks are discussed. It is observed that both the approaches are reasonably good in predicting the real response. However, the equivalent continuum approach has predicted somewhat higher stiffness values at low strains. Considering the modelling effort involved in case of discrete continuum approach, for problems with complex geometry, it is suggested that a proper equivalent continuum model can be used, without compromising much on the accuracy of the results. Then the numerical analysis of a tunnel in Japan is taken up using the continuum approach. The deformations predicted are compared well against the field measurements and the predictions from discontinuum analysis. (C) 2012 Elsevier Ltd. All rights reserved.

Discrete time second order sliding mode observer for uncertain linear multi-output system

This paper presents a second order sliding mode observer (SOSMO) design for discrete time uncertain linear multi-output system. The design procedure is effective for both matched and unmatched bounded uncertainties and/or disturbances. A second order sliding function and corresponding sliding manifold for discrete time system are defined similar to the lines of continuous time counterpart. A boundary layer concept is employed to avoid switching across the defined sliding manifold and the sliding trajectory is confined to a boundary layer once it converges to it. The condition for existence of convergent quasi-sliding mode (QSM) is derived. The observer estimation errors satisfying given stability conditions converge to an ultimate finite bound (within the specified boundary layer) with thickness O(T-2) where T is the sampling period. A relation between sliding mode gain and boundary layer is established for the existence of second order discrete sliding motion. The design strategy is very simple to apply and is demonstrated for three examples with different class of disturbances (matched and unmatched) to show the effectiveness of the design. Simulation results to show the robustness with respect to the measurement noise are given for SOSMO and the performance is compared with pseudo-linear Kalman filter (PLKF). (C) 2013 Published by Elsevier Ltd. on behalf of The Franklin Institute